#pragma once
#include "SomeTool.h"

template <size_t K>
struct ProtoVanEmdeBoas
{
	typedef ProtoVanEmdeBoas<K - 1> Cld;
	static constexpr size_t u = PowN<2, PowN<2, K>>;

	Cld* summary = NULL;
	Cld* cluster[Cld::u] = {};

	bool member(size_t x) const;
	auto min() const->std::optional<size_t>;
	auto successor(size_t x) const->std::optional<size_t>;
	bool insert(size_t x);

private:
	size_t high(size_t x) const { return x / Cld::u; }
	size_t low(size_t x) const { return x % Cld::u; }
	size_t index(size_t x, size_t offset) const { return x * Cld::u + offset; }
};

template <>
struct ProtoVanEmdeBoas<0>
{
	static constexpr size_t u = 2;
	bool arr[u] = {};

	bool member(size_t x) const;
	auto min() const->std::optional<size_t>;
	auto successor(size_t x) const->std::optional<size_t>;
	bool insert(size_t x);
};

#include "ProtoVanEmdeBoasTreeImpl.h"